//编写一个高效的算法来判断 m x n 矩阵中，是否存在一个目标值。该矩阵具有如下特性： 
//
// 
// 每行中的整数从左到右按升序排列。 
// 每行的第一个整数大于前一行的最后一个整数。 
// 
//
// 示例 1: 
//
// 输入:
//matrix = [
//  [1,   3,  5,  7],
//  [10, 11, 16, 20],
//  [23, 30, 34, 50]
//]
//target = 3
//输出: true
// 
//
// 示例 2: 
//
// 输入:
//matrix = [
//  [1,   3,  5,  7],
//  [10, 11, 16, 20],
//  [23, 30, 34, 50]
//]
//target = 13
//输出: false 
// Related Topics 数组 二分查找 
// 👍 230 👎 0

package leetcode.editor.cn;

//Java：搜索二维矩阵
public class P74SearchA2dMatrix {

    /**
     *
     * 思路：矩阵的每行的投个元素二分法比较，找出目标数据应该再的那一行，然后二分法每列比较
     *      似乎可以将整个二维数组拉开当作一个 一维数组来看待，然后用以前的二分法来解决。
     *
     * 执行用时： 0 ms , 在所有 Java 提交中击败了 100.00% 的用户 内存消耗： 39.6 MB , 在所有 Java 提交中击败了 40.40% 的用户
     *
     */
    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        public boolean searchMatrix(int[][] matrix, int target) {
            if (matrix.length == 0 || matrix[0].length == 0) {
                return false;
            }

            // n 行
            int n = matrix.length;
            // m 列
            int m = matrix[0].length;

            int left = 0;
            int right = n - 1;

            int lastBigN = -1;      // 最后一次比目标值小的那行
            int lastLessN = -1;     // 最后一次比目标值大的那行

            while (left <= right) {
                int nMid = (left + right) / 2;
                if (matrix[nMid][0] == target) {
                    return true;
                } else if (matrix[nMid][0] > target) {
                    right = nMid - 1;
                    lastBigN = nMid;
                } else {
                    left = nMid + 1;
                    lastLessN = nMid;
                }
            }

            // 目标行
            int targetN;
            if (lastBigN != -1) {
                targetN = lastBigN - 1;
            } else {
                targetN = lastLessN;
            }

            if (targetN < 0 || targetN >= n) {
                return false;
            }

//            left 列 为目标列
            int start = 0;
            int end = m - 1;
            while (start <= end) {
                int mMid = (start + end) / 2;
                if (matrix[targetN][mMid] == target) {
                    return true;
                } else if (matrix[targetN][mMid] > target) {
                    end = mMid - 1;
                } else {
                    start = mMid + 1;
                }
            }
            return false;
        }
    }
    //leetcode submit region end(Prohibit modification and deletion)

    public static void main(String[] args) {
        int[][] nums = new int[][]{
                {}
        };
        Solution solution = new P74SearchA2dMatrix().new Solution();
        System.out.println(solution.searchMatrix(nums, 3));

        for (int i = 0; i <= 50; i++) {
            System.out.println(i + ":" + solution.searchMatrix(nums, i));
        }
        // TO TEST
    }

}